#include <stdio.h>
#include <stdlib.h>

#define maxSize 6

typedef struct doubleLinkedList{
    struct doubleLinkedList * prior;
    int data;
    struct doubleLinkedList * next;
}DoubleLinkedList;

//双链表的创建函数
DoubleLinkedList * initDoubleLinkedList(DoubleLinkedList * head);

//输出双链表的函数
void displayDoubleLinkedList(DoubleLinkedList* head);

//双链表插入元素，index表示插入位置
DoubleLinkedList * insertDoubleLinkedList(DoubleLinkedList * head, int data, int index);

//双链表删除指定元素
DoubleLinkedList * delDoubleLinkedList(DoubleLinkedList * head, int elem);

//双链表中查找指定元素
int searchDoubleLinkedList(DoubleLinkedList * head, int elem);

//双链表中更改指定位置节点中存储的数据，index表示更改位置
DoubleLinkedList * updateDoubleLinkedList(DoubleLinkedList * head, int index, int newElem);

int main(int argc, char* argv[]) {
    //创建一个头指针
    DoubleLinkedList * head = NULL;
    //调用链表创建函数
    head = initDoubleLinkedList(head);
    //输出创建好的链表
    displayDoubleLinkedList(head);

    //在表中第 3 的位置插入元素 7
    head = insertDoubleLinkedList(head, 7 , 3);
    displayDoubleLinkedList(head);

    //表中删除元素 2
    head = delDoubleLinkedList(head, 2);
    displayDoubleLinkedList(head);

    printf("元素 3 的位置是：%d\n",searchDoubleLinkedList(head,3));

    //表中第 3 个节点中的数据改为存储 6
    head = updateDoubleLinkedList(head, 3, 6);
    displayDoubleLinkedList(head);
}


//双链表的创建函数
DoubleLinkedList * initDoubleLinkedList(DoubleLinkedList * head) {
    //创建一个首元节点，链表的头指针为head
    head = (DoubleLinkedList *)malloc(sizeof(DoubleLinkedList));
    head->prior = NULL;
    head->next = NULL;
    head->data = 1;

    //声明一个指向首元节点的指针，方便后期向链表中添加新创建的节点
    DoubleLinkedList * tempHead = head;
    for(int i=2; i<maxSize; i++) {
        DoubleLinkedList * list = (DoubleLinkedList *)malloc(sizeof(DoubleLinkedList));
        //新节点与链表最后一个节点建立关系
        list->prior = tempHead;
        list->next = NULL;
        list->data = i;
        //链表中最后一个节点tempHead指向新节点list
        tempHead->next = list;
        //tempHead永远指向链表中最后一个节点
        tempHead = tempHead->next;
    }
    //返回新创建的链表
    return head;
}

//输出双链表的函数
void displayDoubleLinkedList(DoubleLinkedList* head) {
    //声明一个指向首元节点的指针
    DoubleLinkedList * tempHead = head;
    while(tempHead) {
        if(tempHead->next) {
            printf("%d <-> ", tempHead->data);
        } else {
            printf("%d\n", tempHead->data);
        }
        tempHead = tempHead->next;
    }
    
}

//双链表插入元素，index表示插入位置
DoubleLinkedList * insertDoubleLinkedList(DoubleLinkedList * head, int data, int index) {
    //新建数据域为data的结点
    DoubleLinkedList * temp = (DoubleLinkedList *)malloc(sizeof(DoubleLinkedList));
    temp->prior = NULL;
    temp->data = data;
    temp->next = NULL;
    //添加至双链表
    //插入到链表头
    if(index == 1) {
        temp->next = head;
        head->prior = temp;
        head = temp;
    } else {
        DoubleLinkedList * tempHead = head;
        //找到要插入位置的前一个结点
        for(int i=1; i<index-1; i++) {
            tempHead = tempHead->next;
        }
        //判断是否尾节点
        if(tempHead->next == NULL) {
            tempHead->next = temp;
            temp->prior = tempHead;
        } else {
            //插入位置的prior指向新元素节点，新元素节点next指向插入位置
            tempHead->next->prior = temp;
            temp->next = tempHead->next;
            //插入位置的前一个结点next指向新元素节点，新元素节点的prior指向插入位置的前一个结点
            tempHead->next = temp;
            temp->prior = tempHead;
        }
    }
    return head;
}

//双链表删除指定元素
DoubleLinkedList * delDoubleLinkedList(DoubleLinkedList * head, int elem) {
    //创建临时结点tempHead,指向头结点
    DoubleLinkedList * tempHead = head;
    //遍历链表
    while (tempHead)
    {
        /* 判断当前结点中数据域和elem是否相等，若相等，摘除该结点 */
        if (tempHead->data == elem)
        {
            /* 删除位置前一个结点的next指向其后一个结点 */
            tempHead->prior->next = tempHead->next;
            /* 删除位置后一个结点的prior指向其前一个结点 */
            tempHead->next->prior = tempHead->prior;
            //释放删除位置
            free(tempHead);
            return head;
        }
        tempHead = tempHead->next;
    }
    printf("链表中无该数据元素");
    return head;    
}

//双链表中查找指定元素
int searchDoubleLinkedList(DoubleLinkedList * head, int elem) {
    //创建临时结点tempHead,指向头结点
    DoubleLinkedList * tempHead = head;
    int i = 1;
    //遍历链表
    while (tempHead)
    {
        /* 判断当前结点中数据域和elem是否相等，若相等，返回该结点位置 */
        if (tempHead->data == elem)
        {
            return i;
        }
        i++;
        tempHead = tempHead->next;
    }
    printf("链表中无该数据元素");
    return -1;
}

//双链表中更改指定位置节点中存储的数据，index表示更改位置
DoubleLinkedList * updateDoubleLinkedList(DoubleLinkedList * head, int index, int newElem) {
    //创建临时结点tempHead,指向头结点
    DoubleLinkedList * tempHead = head;
    //遍历到被更新结点
    for(int i=1; i<index; i++) {
        tempHead = tempHead->next;
    }
    tempHead->data = newElem;
    return head;
}